//给你一个字符串 s，找到 s 中最长的回文子串。
//
//
//
// 示例 1：
//
//
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
//
//
// 示例 2：
//
//
//输入：s = "cbbd"
//输出："bb"
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 1000
// s 仅由数字和英文字母组成
//
// Related Topics 字符串 动态规划 👍 5379 👎 0

package leetcode.editor.cn;

class 最长回文子串 {
    public static void main(String[] args) {
        Solution solution = new 最长回文子串().new Solution();
        String s = solution.longestPalindrome("abcbachdchdhcd");
        System.out.println(s);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String longestPalindrome(String str) {
            if (str == null || str.length() == 0) {
                return "";
            }
            char[] charArr = manacherString(str);
            int[] pArr = new int[charArr.length];
            int index = -1;
            int pR = -1;
            int max = Integer.MIN_VALUE;
            int mid = 0;
            for (int i = 0; i != charArr.length; i++) {
                pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
                while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
                    if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) {
                        pArr[i]++;
                    } else {
                        break;
                    }
                }
                if (i + pArr[i] > pR) {
                    pR = i + pArr[i];
                    index = i;
                }
                if (max < pArr[i]) {
                    max = pArr[i];
                    mid = i;
                }
            }
            mid = (mid - 1) / 2;
            max = max - 1;
            return str.substring((max & 1) == 0 ? mid - (max / 2) + 1 : mid - (max / 2), mid + (max / 2) + 1);
        }

        public char[] manacherString(String str) {
            char[] charArr = str.toCharArray();
            char[] res = new char[str.length() * 2 + 1];
            int index = 0;
            for (int i = 0; i != res.length; i++) {
                res[i] = (i & 1) == 0 ? '#' : charArr[index++];
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}
